/************************************* A S S I G N M E N T ****************************************
*                                TEACHER : Dr K. Mukhopadhyay.
*                                STUDENT : Abhay kumar. ( mtc0415).
*
****************************************************************************************************/
#include <stdio.h>
#define MAX 100   // maximum stack....
//********************************************************************************************
struct Stack
{
    int val;
    int node1;
    int node2;
};
//*************************************************************************************************
struct Node_G
{
    int high_value;
    int dfs_n;
    int parent;
};

//*************************************************************************************************
int Top = 0, dfs_current;
char  **adj_mat;
struct Stack     p_stk[MAX];
struct Node_G   *nodes;
//*************************************************************************************************
void Push(struct Stack item)
{
   
    p_stk[Top].val = item.val;
    p_stk[Top].node1 = item.node1;
    p_stk[Top].node2 = item.node2;
    Top++;
}
//*************************************************************************************************
void Pop(struct Stack *z)
{
    Top = Top - 1;
    z->val = p_stk[Top].val;
    z->node1 = p_stk[Top].node1;
    z->node2 = p_stk[Top].node2;
}
//*************************************************************************************************
int Get_biconnected(int count, int n_node)
{
    struct Stack node_c;
    int counter;
    int flag = 0 ;
//--------------------------------------------------------------------------------------------------
    // Giving DFS Number ....
    nodes[count].DFS_Number = dfs_current;
    dfs_current = dfs_current - 1;
 //-------------------------------------------------------------------------------------------------   
    // pushing the current node in the stack ......
    node_c.val = 1;
    node_c.node1 = count;
    node_c.node2 = 0;
    Push(node_c);
    nodes[count].high_value = nodes[count].dfs_n
  //------------------------------------------------------------------------------------------------  
    //verifying all edges of the current node......
    for(counter = 0;counter < n_node; counter++)
    {
        if(adj_mat[count][counter] == 1)
        {
            //inserting the edge .......
            node_c.val = 2;
            node_c.node1 = count;
            node_c.node2 = counter;

            Push(node_c);
            if(nodes[count].parent != counter) 
            {
                if(nodes[counter].DFS_Number == 0) 
                {
                    nodes[counter].parent = count;
                    Get_biconnected(counter, n_node);

                    //popping all nodes......
                    if(nodes[counter].high_value <= nodes[count].DFS_Number)
                    {
			if(flag == 0)
			  {
                        	printf("\n The graph has bi-Connected component....\n");
				printf(" The vertices  of the component are.... \n");
			  	flag++;	
			  }
				printf("\n\n\n");
                        Pop(&node_c);
                        while(node_c.val != 1 || node_c.node1 != count)
                        {
                            
                            if(node_c.val == 1)
                                printf("%d\t", (node_c.node1 + 1));
                           
                            Pop(&node_c);                        
                        }

                        printf("%d", (node_c.node1 + 1));
                        // pushing the node in the stack
                        Push(node_c);
                    }
			if( nodes[count].high_value > nodes[counter].high_value )
			  {
			    s[count].high_value =nodes[count].high_value;
			  }
			else
			    s[count].high_value =nodes[counter].high_value;
                  } 
               else
               {
			if( nodes[count].high_value > nodes[counter].DFS_Number)
			  {
			    nodes[count].high_value =nodes[count].high_value;
			  }
			else
			    nodes[count].high_value =nodes[counter].dfs_n;

                }
                   
            }

            
            
        }
            
        
    }      

}
//*************************************************************************************************
//Main proceedings starts in main...............
int main()
{
	int opt = 1;
        int counter, n_node, node1, node2;
    	int flag = 0;
//--------------------------------------------------------------------------------------------------
    printf("\n Enter the Node_G number of the Graph.... ");
    scanf("%d", &n_node);
//--------------------------------------------------------------------------------------------------
 
    nodes = (struct Node_G *)calloc(n_node, sizeof(struct Node_G));
    adj_mat = (char **)calloc(n_node, sizeof(char *));
//--------------------------------------------------------------------------------------------------
    for(counter = 0;counter < n_node; counter++)
    {
        adj_mat[counter] = (char *)calloc(n_node, sizeof(char));
        nodes[counter].parent = -1;
    }

    nodes[0].parent = 0;
//---------------------------------------------------------------------------------------------------
    printf("\n Enter the edges of the graph....\n");
//--------------------------------------------------------------------------------------------------   
    while(opt!= 0)
    {
        printf("\n Enter  Node1    Node2..... ");
        scanf("%d%d",&node1,&node2);
        fflush(stdin);
        
          
       
        adj_mat[node1 - 1][node2 - 1] = 1;
        adj_mat[node2 - 1][node1 - 1] = 1;
	printf("Do you want to continue (0/1).....");
	scanf("%d",&opt);
       
    }
//--------------------------------------------------------------------------------------------------    
    // Initializing max DFS number 
    dfs_current = n_node;
    Get_biconnected(0, n_node);
    printf("\n");     
}

//*************************************************************************************************
/*                                   R E S U L T S :

 
[mtc0415@mtech02 mtc0415]$ ./a.out
 
 Enter the Node_G number of the Graph.... 4
 
 Enter the edges of the graph....
 
 Enter  Node1    Node2..... 1   2
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 1   3
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 2   3
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 1   4
Do you want to continue (0/1).....0
 
 The graph has bi-Connected component....
 The vertices  of the component are....
 
 
 
3       2       1
The graph has bi-Connected component....
 The vertices  of the component are....
  
 
4       1
[mtc0415@mtech02 mtc0415]$ ./a.out
 
 Enter the Node_G number of the Graph.... 6
 
 Enter the edges of the graph....
 
 Enter  Node1    Node2..... 1   2
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 1   3
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 1   4
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 2   3
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 2   4
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 3   4
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 4   5
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 4   6
Do you want to continue (0/1).....1
 
 Enter  Node1    Node2..... 5   6
Do you want to continue (0/1).....0
 
 The graph has bi-Connected component....
 The vertices  of the component are....
 
 
 
6       5       4
 The graph has bi-Connected component....
 The vertices  of the component are....
 
 
 
4       3       2       1
[mtc0415@mtech02 mtc0415]$

*/
